package leetcode;

import java.util.Stack;

/**
 * Leetcode503【下一个更大元素 II】
 * https://leetcode-cn.com/problems/next-greater-element-ii/
 */
public class NextGreaterElementsTwo {
    private int head;
    private int tail;
    public int[] nextGreaterElements(int[] nums) {
        int[] ret = new int[nums.length];
        int count = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            head = i;
            tail = (head + 1) % nums.length;
            while (nums[tail] <= nums[head] && tail != head) {
                tail = (tail + 1) % nums.length;
            }
            if (tail == head) {
                ret[count] = -1;
                count--;
            } else {
                ret[count] = nums[tail];
                count--;
            }
        }
        return ret;
    }
}
